\chapter{Moments and Inequalities}
\section{Quicksort}
\textbf{Problem}\\
Given $n$,for any $1 \leq i \leq j \leq n$,define Bernoulli random variable $Y_{ij}$ s.t. $Pr(Y_{ij}=1)=\frac{2}{j-i-1}$.Let $X=\sum_{1 \leq i < j \leq n}^{}Y_{ij}$.Prove that $E(X) \leq 2n \ln n+O(n)$.\\\\
\textbf{Solution}
	\begin{proof}
		\begin{eqnarray*}
		E(X)
		&=& E\left (\sum_{1 \leq i < j \leq n}^{}Y_{ij}\right)\\
		&=& \sum_{1\leq{i}<j \leq n}^{}E \left(Y_{ij}\right)\\
		&=& \sum_{1\leq{i}<j \leq n}^{}\frac{2}{j-i+1}\\
		&=& 2 \left[{\frac{1}{2} + \left(\frac{1}{2}+\frac{1}{3} \right)+\cdots+ \left(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} \right)}\right]\\
		&=& 2 \left(\frac{n-1}{2}+\frac{n-2}{3}+\cdots+\frac{2}{n-1}+\frac{1}{n} \right)\\
		&\leq & 2 \left(n-1 \right) \left(\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n} \right)\\
		&=& 2 \left(n-1 \right) \left({\rm ln}n+C \right)\\
		&=& 2 n \left({\rm ln}n+C \right)\\
		&=& 2 n {\rm ln}n+O(n)
	\end{eqnarray*}
Such that the proof ends.
	\end{proof}

\section{Markov's Inequality} 
\textbf{Problem}\\
Prove the following extensions of the Chernoff bound. Let $X=\sum_{i=1}^{n} X_i$, where the $X_i$ are independent 0-1 random variables. Let $\mu = E[X]$. Choose any $\mu_L$ and $\mu_H$ such that $\mu_L \le \mu \le \mu_H$. Then, for any $\delta > 0$, $Pr(X \ge (1+\delta) \mu_H) \le (\frac{e^\delta}{(1+\delta)^{(1+\delta)}}) \mu_H$.
Similarly, for any $0 < \delta < 1$, $Pr(X \le (1-\delta) \mu_L) \le (\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}) \mu_L$.\\\\
\textbf{Solution}\\
\begin{proof}
	At first we will prove
\begin{eqnarray*}
	E[e^{tX}]
	&=& E\left[e^{t\sum_{i=1}^{n}X_i} \right]\\
	&=& E \left[t \prod_{i=1}^{n}X_i \right]\\
	&=& \prod_{i=1}^{n}E \left[e^{tX_i} \right]\\
	&=& \prod_{i=1}^{n}\left(p_i\cdot e^t +(1-p_i)\cdot 1 \right)\\
	&=& \prod_{i=1}^{n}(1+p_i(e^t-1))\\
	&\leq& \prod_{i=1}^{n}e^{p_i(e^t-1)}\\
	&=& e^{\sum_{i=1}^{n}p_i(e^t-1)}\\
	&=& e^{(e^t-1)\mu}\\
	&\leq& e^{(e^t-1)\mu_H}
\end{eqnarray*}
\textbf{First inequality proof}\\
Apply Markov's inequality, for any $t>0$ we have
\begin{equation*}
\begin{split}
Pr\left(X \ge (1+\delta) \mu_H\right) &= Pr\left(e^{tX} \ge e^{t(1+\delta)\mu_H}\right)\\
&\le \frac{E[e^{tX}]}{e^{t(1+\delta)\mu_H}} \\
&\le \frac{e^{(e^t-1)\mu}}{e^{t(1+\delta)\mu_H}} \\
&\le \frac{e^{(e^t-1)\mu_H}}{e^{t(1+\delta)\mu_H}}
\end{split}
\end{equation*}
For any $\delta>0$, we can set $t=\ln(1+\delta)$ then
\begin{equation*}
\begin{split}
Pr(X \ge (1+\delta) \mu_H) &\le \frac{e^{(e^t-1)\mu_H}}{e^{t(1+\delta)\mu_H}} \\
&= \left(\frac{e^\delta}{(1+\delta)^{(1+\delta)}}\right) \mu_H
\end{split}
\end{equation*}
\textbf{Second inequality proof}\\
Apply Markov's inequality, for any $t<0$ we have
\begin{equation*}
\begin{split}
Pr(X \le (1-\delta) \mu_L) &= Pr\left(e^{tX} \ge e^{t(1-\delta)\mu_L}\right)\\
&\le \frac{E[e^{tX}]}{e^{t(1-\delta)\mu_L}} \\
&\le \frac{e^{(e^t-1)\mu}}{e^{t(1-\delta)\mu_L}} \\
&\le \frac{e^{(e^t-1)\mu_L}}{e^{t(1-\delta)\mu_L}}
\end{split}
\end{equation*}
For any $0<\delta<1$, we can set $t=\ln(1-\delta)<0$ then
\begin{equation*}
\begin{split}
Pr(X \le (1-\delta) \mu_L) &\le \frac{e^{(e^t-1)\mu_L}}{e^{t(1-\delta)\mu_L}} \\
&= \left(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}}\right) \mu_L
\end{split}
\end{equation*}
\end{proof}

\section{Moment and Chernoff Bound}
\textbf{Problem}\\
Let $X_1, \cdots X_n$ be independent Poisson trials such that $Pr(X_i = 1) = p_i$ and let $a_1, \cdots a_n$ be real numbers in $[0, 1]$. let $X = \sum_{i=1}^{n} a_iX_i$ and $\mu = E[X]$. Then the following Chernoff bound holds: for any $\delta > 0$, $Pr(X \ge (1+\delta) \mu) \le (\frac{e^\delta}{(1+\delta)^{(1+\delta)}})^\mu$. Also prove a similar bound for the probability $Pr(X \le (1-\delta)\mu)$ for any $0 < \delta < 1$.\\\\
\textbf{Solution}\\
\begin{proof}
	First we can see that $\mu=E[X]=\sum_{i=1}^{n} a_ip_i$, and use this to calculate $M_X(t)$. We can see that $M_{X_i}(t) = 1+p_i(e^t-1)$, so
\begin{equation*}
\begin{split}
E(e^{tX}) = M_X(t) &= \prod_{i=1}^{n} (a_i + a_i p_i (e^t-1)) \\
&\le \prod_{i=1}^{n} (1 + a_i p_i (e^t-1)) \\
&\le \prod_{i=1}^{n} e^{a_i p_i (e^t-1)} \\
&= e^{\sum_{i=1}^{n} a_i p_i (e^t-1)} \\
&= e^{(e^t-1)\mu}
\end{split}
\end{equation*}

Then we get the same the product of the n generating functions as the independent Poisson trials has. So we get the same Chernoff bound.
That is to say
$Pr(X \ge (1+\delta) \mu) \le (\frac{e^\delta}{(1+\delta)^{(1+\delta)}})^\mu$ for any $\delta>0$ and  $Pr(X \le (1-\delta)\mu)\le (\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}})^\mu$ for any $0 < \delta < 1$.
\end{proof}

\section{Convex Function and Chernoff Bound}
\textbf{Problem}\\
Recall that a function $f$ is said to be convex if, for any $x_1, x_2$ and for $0 \le \lambda \le 1$, $f(\lambda x_1 + (1-\lambda) x_2) \le \lambda f(x_1)+ (1-\lambda) f(x_2)$.
\begin{itemize}
	\item Let $Z$ be a random variable that takes on a finite set of values in $[0, 1]$, and let $p = E[Z]$. Define the Bernoulli random variable $X$ by $Pr(X = 1) = p$ and $Pr(X = 0) = 1-p$. Show that $E[f(Z)] \le E[f(X)]$ for any convex function $f$.
	\item Use the fact that $f(x) = e^{tx}$ is convex for any fixed $t \ge 0$ to obtain a Chernoff-like bound for $Z$.\\
\end{itemize}
\textbf{Solution}\\
\begin{proof}
	\begin{itemize}
\item According to convex definition,we have
\begin{eqnarray*}
	E[f(Z)]
	&=& \sum_{i=1}^{n}f(z_i)p_i\\
	&=& \sum_{i=1}^{n}((1-z_i)\cdot 0+z_i\cdot 1)p_i)\\
	&\leq & \sum_{i=1}^{n} \left((1-z_i)f(0)+z_i f(1)p_i \right)\\
	&=& \left(1-\sum_{i=1}^{n}p_iz_i \right)f(0)+\sum_{i=1}^{n}p_iz_if(1)\\
	&=& (1-E[Z])f(0)+E[Z]f(1)\\
	&=& E[f(X)].
\end{eqnarray*}
Such that the proof ends.
\item Simply we have $E[e^{tX}] = (1-p) + pe^t$.
 According to \textit{Markov's} inequality, for any $t>0$ we have
 \begin{eqnarray*}
 Pr(Z \ge a) 
 &=& Pr(e^{tZ}\ge e^{ta})\\
 &\le& \frac{E(e^{tZ})}{e^{ta}} \\
 &\le & \frac{E(e^{tX})}{e^{ta}}\\
 &=& \frac{pe^t-p+1}{e^{ta}}
 \end{eqnarray*}
 So we have $Pr(Z \ge a) \le \frac{pe^t-p+1}{e^{ta}}$ for any $t>0$ as a \textit{Chernoff}-like bound.
\end{itemize}
\end{proof}

\section{Coin}
\textbf{Problem}\\
Do Bernoulli experiment for 20 trials, using a new 1-Yuan coin.Write down the results in a string $s_1 s_2 \cdots s_{20}$, where $s_i$ is 1 if the $i$-th trial gets Head,and otherwise is 0.
\\
\textbf{Solution}\\
The result of tossing a coin 20 times is:\\11101000111010101000.

